package com.cat.binaryTree;

import java.lang.reflect.Parameter;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/lowest-common-ancestor-of-deepest-leaves/https://leetcode.cn/problems/lowest-common-ancestor-of-deepest-leaves/
 * @create 2025/9/15 19:18
 * @since JDK17
 */



public class Solution45 {
    int depth;
    int depth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return 1 + Math.max(depth(root.left), depth(root.right));
    }

    TreeNode f(TreeNode root, int cur) {
        if (root == null) {
            return null;
        }
        if (root.left == null && root.right == null && cur == depth) {
            return root;
        }
        TreeNode l = f(root.left, cur + 1);
        TreeNode r = f(root.right, cur + 1);
        if (l != null && r != null) {
            return root;
        }
        if (l != null) {
            return l;
        }
        return r;
    }
    Pair<Integer, TreeNode> dfs(TreeNode root) {
        if (root == null) {
            return new Pair<>(0, null);
        }
        var l = dfs(root.left);
        var r = dfs(root.right);
        if (l.getKey() > r.getKey()) {
            return l;
        } else if (l.getKey() < r.getKey()) {
            return r;
        } else {
            return new Pair<>(l.getKey() + 1, root);
        }
    }

    public TreeNode lcaDeepestLeaves(TreeNode root) {
//        depth = depth(root);
//        return f(root, 0);
        return dfs(root).getValue();
    }

}
